package chapter7.graph;

/**
 * Created by lili on 2017/7/1.
 */
//【例7.3】  构造带权无向图G5的最小生成树。

public class WeightedUndiG5
{
    public static void main(String args[])
    {
        String[] vertices={"A","B","C","D","E"};           //带权无向图G5的顶点集合
        Edge edges[]={new Edge(0,1,25), new Edge(0,2,4), new Edge(0,3,22),
                new Edge(1,0,25), new Edge(1,2,16), new Edge(1,4,3),
                new Edge(2,0,4), new Edge(2,1,16), new Edge(2,3,18), new Edge(2,4,7),
                new Edge(3,0,22), new Edge(3,2,18), new Edge(3,4,9),
                new Edge(4,1,3), new Edge(4,2,7), new Edge(4,3,9)}; //G5的边集合
//        AdjMatrixGraph<String> graph = new AdjMatrixGraph<String>(vertices, edges);
        AdjListGraph<String> graph = new AdjListGraph<String>(vertices, edges);
//        System.out.println("带权无向图G5，"+graph.toString());
//        graph.minSpanTree_prim();                          //构造带权图最小生成树的普里姆算法
        graph.shortestPath(0);               //顶点A的单源最短路径，Dijkstra算法
//        for (int i=0; i<graph.vertexCount(); i++)
//            graph.shortestPath(i);               //顶点vi的单源最短路径，Dijkstra算法

    }
}
/*
程序运行结果如下：
带权无向图G5，顶点集合：(A, B, C, D, E)
邻接矩阵:
  0  25  4  22  ∞
  25  0  16  ∞  3
  4  16  0  18  7
  22  ∞  18  0  9
  ∞  3  7  9  0
带权无向图G5，出边表：
(A：((0,1,25), (0,2,4), (0,3,22)),
B：((1,0,25), (1,2,16), (1,4,3)),
C：((2,0,4), (2,1,16), (2,3,18), (2,4,7)),
D：((3,0,22), (3,2,18), (3,4,9)),
E：((4,1,3), (4,2,7), (4,3,9)))

mst数组初值：(0,1,25)(0,2,4)(0,3,22)(0,4,99999)
mst数组：(0,2,4)(2,1,16)(2,3,18)(2,4,7)
mst数组：(0,2,4)(2,4,7)(4,3,9)(4,1,3)
mst数组：(0,2,4)(2,4,7)(4,1,3)(4,3,9)
mst数组：(0,2,4)(2,4,7)(4,1,3)(4,3,9)
最小生成树的边集合：(0,2,4) (2,4,7) (4,1,3) (4,3,9) ，最小代价为23
*/

/*
程序运行结果如下：
带权无向图G6，顶点集合：{A, B, C, D, E}
邻接矩阵:
  0  5  4  12  ∞
  5  0  6  ∞  7
  4  6  0  8  3
  12  ∞  8  0  9
  ∞  7  3  9  0

mst数组：(0,1,5)(0,2,4)(0,3,12)(0,4,2147483647)
mst数组：(0,2,4)(0,1,5)(2,3,8)(2,4,3)
mst数组：(0,2,4)(2,4,3)(2,3,8)(0,1,5)
mst数组：(0,2,4)(2,4,3)(0,1,5)(2,3,8)

最小生成树，顶点集合：{A, B, C, D, E}
邻接矩阵:
  0  5  4  ∞  ∞
  ∞  0  ∞  ∞  ∞
  ∞  ∞  0  8  3
  ∞  ∞  ∞  0  ∞
  ∞  ∞  ∞  ∞  0

        AbstractGraph<String> minspantree = graph.minSpanTree_prim();
        System.out.println("\n最小生成树，"+minspantree.toString());
*/
/*

vset数组{1,0,0,0,0}	path数组{-1,0,0,0,-1}	dist数组{0,25,4,22,2147483647}
vset数组{1,0,1,0,0}	path数组{-1,2,0,0,2}	dist数组{0,20,4,22,11}
vset数组{1,0,1,0,1}	path数组{-1,4,0,4,2}	dist数组{0,14,4,20,11}
vset数组{1,1,1,0,1}	path数组{-1,4,0,4,2}	dist数组{0,14,4,20,11}
vset数组{1,1,1,1,1}	path数组{-1,4,0,4,2}	dist数组{0,14,4,20,11}
从顶点A到其他顶点的最短路径如下：
(A,C,E,B)长度为14
(A,C)长度为4
(A,C,E,D)长度为20
(A,C,E)长度为11

vset数组{0,1,0,0,0}	path数组{1,-1,1,-1,1}	dist数组{25,0,16,2147483647,3}
vset数组{0,1,0,0,1}	path数组{1,-1,4,4,1}	dist数组{25,0,10,12,3}
vset数组{0,1,1,0,1}	path数组{2,-1,4,4,1}	dist数组{14,0,10,12,3}
vset数组{0,1,1,1,1}	path数组{2,-1,4,4,1}	dist数组{14,0,10,12,3}
vset数组{1,1,1,1,1}	path数组{2,-1,4,4,1}	dist数组{14,0,10,12,3}
从顶点B到其他顶点的最短路径如下：
(B,E,C,A)长度为14
(B,E,C)长度为10
(B,E,D)长度为12
(B,E)长度为3

vset数组{0,0,1,0,0}	path数组{2,2,-1,2,2}	dist数组{4,16,0,18,7}
vset数组{1,0,1,0,0}	path数组{2,2,-1,2,2}	dist数组{4,16,0,18,7}
vset数组{1,0,1,0,1}	path数组{2,4,-1,4,2}	dist数组{4,10,0,16,7}
vset数组{1,1,1,0,1}	path数组{2,4,-1,4,2}	dist数组{4,10,0,16,7}
vset数组{1,1,1,1,1}	path数组{2,4,-1,4,2}	dist数组{4,10,0,16,7}
从顶点C到其他顶点的最短路径如下：
(C,A)长度为4
(C,E,B)长度为10
(C,E,D)长度为16
(C,E)长度为7

vset数组{0,0,0,1,0}	path数组{3,-1,3,-1,3}	dist数组{22,2147483647,18,0,9}
vset数组{0,0,0,1,1}	path数组{3,4,4,-1,3}	dist数组{22,12,16,0,9}
vset数组{0,1,0,1,1}	path数组{3,4,4,-1,3}	dist数组{22,12,16,0,9}
vset数组{0,1,1,1,1}	path数组{2,4,4,-1,3}	dist数组{20,12,16,0,9}
vset数组{1,1,1,1,1}	path数组{2,4,4,-1,3}	dist数组{20,12,16,0,9}
从顶点D到其他顶点的最短路径如下：
(D,E,C,A)长度为20
(D,E,B)长度为12
(D,E,C)长度为16
(D,E)长度为9

vset数组{0,0,0,0,1}	path数组{-1,4,4,4,-1}	dist数组{2147483647,3,7,9,0}
vset数组{0,1,0,0,1}	path数组{1,4,4,4,-1}	dist数组{28,3,7,9,0}
vset数组{0,1,1,0,1}	path数组{2,4,4,4,-1}	dist数组{11,3,7,9,0}
vset数组{0,1,1,1,1}	path数组{2,4,4,4,-1}	dist数组{11,3,7,9,0}
vset数组{1,1,1,1,1}	path数组{2,4,4,4,-1}	dist数组{11,3,7,9,0}
从顶点E到其他顶点的最短路径如下：
(E,C,A)长度为11
(E,B)长度为3
(E,C)长度为7
(E,D)长度为9

*/

